//
// Description: 93. 复原 IP 地址
// Created by Loading on 2022/5/2.
//

#include <bits/stdc++.h>

using namespace std;

vector<string> restoreIpAddresses(string s) {
    vector<string> res;
    int n = s.size();
    if (n < 4 || n > 12) {
        return res;
    }

    // 存储四段ip地址的值
    vector<int> ipSeg(4);
    function<void(int, int)> dfs = [&](int segId, int startIndex) {
        // 4 段遍历完成
        if (segId == 4) {
            // 正好遍历到结尾，加入结果集
            if (startIndex == n) {
                string ip;
                for (int i = 0; i < 4; ++i) {
                    ip += to_string(ipSeg[i]) + ".";
                }
                ip.pop_back();
                res.emplace_back(ip);
            }
            return;
        }

        // 未遍历完 4 段就到了结尾
        if (startIndex == n) {
            return;
        }

        // 存在前导 0 时，该段只能是 0
        if (s[startIndex] == '0') {
            ipSeg[segId] = 0;
            dfs(segId + 1, startIndex + 1);
        }

        // 一般情况
        int addr = 0;
        for (int i = startIndex; i < n; ++i) {
            addr = addr * 10 + s[i] - '0';
            /* 注意 addr 要大于 0，因为等于 0 的情况已经在上面计算过 */
            if (addr > 0 && addr <= 255) {
                ipSeg[segId] = addr;
                dfs(segId + 1, i + 1);
            } else {
                break;
            }
        }
    };

    dfs(0, 0);

    return res;
}

int main() {
    string s = "0000";
    auto res = restoreIpAddresses(s);
    for (auto tmp : res) {
        cout << tmp << endl;
    }

    return 0;
}